package xin.yangshuai.leetcode01.question39;

import java.util.ArrayList;
import java.util.List;

public class Question39 {

    public static void main(String[] args) {
        Question39.Solution solution = new Question39().new Solution();

        int[] candidates = {2, 3, 6, 7};
        int target = 7;

        List<List<Integer>> list = solution.combinationSum(candidates, target);
        System.out.println(list);
    }

    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {

            // 从小到大排序
            for (int i = 0; i < candidates.length - 1; i++) {
                for (int j = i + 1; j < candidates.length; j++) {
                    int a = candidates[i];
                    int b = candidates[j];
                    if (a > b) {
                        candidates[i] = b;
                        candidates[j] = a;
                    }
                }
            }

            int length = candidates.length;
            int[] maxArray = new int[length];
            for (int i = 0; i < length; i++) {
                int candidate = candidates[i];
                // 如果只有当前这个数，最多有几个
                int count = target / candidate;
                maxArray[i] = count;
            }
            int[] countArray = new int[length];

            List<List<Integer>> list = new ArrayList<>();

            while (countArray[length - 1] <= maxArray[length - 1]) {
                int sum = 0;
                List<Integer> targetList = new ArrayList<>();
                for (int i = length - 1; i >= 0; i--) {
                    int count = countArray[i];
                    sum = sum + candidates[i] * count;
                    // 如果大于target，则无需低位的循环，将当前位置的后一位数量+1，当前位及低位数量置为0
                    if (sum > target) {
                        countArray[i + 1] = countArray[i + 1] + 1;
                        for (int j = 0; j < i + 1; j++) {
                            countArray[j] = 0;
                        }
                        break;
                    }
                    int num = 1;
                    while (num <= count) {
                        targetList.add(candidates[i]);
                        num++;
                    }
                }
                // 中途跳出的sum一定大于target
                if (sum == target) {
                    list.add(targetList);
                    // 进行下一次循环
                    countArray[0] = countArray[0] + 1;
                } else if (sum < target) {
                    // 进行下一次循环
                    countArray[0] = countArray[0] + 1;
                }
                for (int i = 0; i < length; i++) {
                    if (countArray[i] == maxArray[i] + 1) {
                        if (i < length - 1) {
                            countArray[i + 1] = countArray[i + 1] + 1;
                            countArray[i] = 0;
                        }
                    }
                }
            }
            return list;
        }
    }
}
